package demo1;

import java.util.Stack;

public class Sort {
    public static  void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]){
                    swap(arr,i,j);
                }
            }
        }
    }
    private static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    public static void quickSort1(int[] arr){
        quick(arr,0,arr.length-1);
    }
    public static void quickSort2(int[] arr){
        quick2(arr);
    }
    //非递归快排
    private static void quick2(int[] arr){
        int left=0;
        int right=arr.length-1;
        int par=partition1(arr,left,right);
        Stack<Integer> stack=new Stack<>();
        //超过两个的数组我们才去判 一个的话不用管他了
        if(par-left+1>=3){
            stack.push(left);
            stack.push(par-1);
        }
        if(right-par+1>=3){
            stack.push(par+1);
            stack.push(right);
        }
        while (!stack.isEmpty()){
            right=stack.pop();
            left=stack.pop();
            par=partition1(arr,left,right);
            if(par-left+1>=3){
                stack.push(left);
                stack.push(par-1);
            }
            if(right-par+1>=3){
                stack.push(par+1);
                stack.push(right);
            }
        }
    }
    //递归快排
    private static void quick(int[] arr,int left,int right){
        if(left>=right) return;
        if(right-left+1==5){
            insertSort(arr,left,right);
            return;
        }
        int mid=numThreeMax(arr,left,right);
        swap(arr,left,mid);
        int par=partition2(arr,left,right);
        quick(arr,left,par-1);
        quick(arr,par+1,right);
    }
    private static void insertSort(int[] arr,int left,int right){
        for (int i = left+1; i <=right ; i++) {
            int temp=arr[i];
            int j=i-1;
            for(;j>=left;j--){
                if(arr[j]>temp){
                    arr[j+1]=temp;
                }else{
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
    private static int numThreeMax(int[] arr,int left,int right){
        int mid=(left+right)/2;
        if(arr[left]<arr[right]){
            if(arr[mid]<arr[left]){
                return left;
            }
            else if(arr[mid]>arr[right]){
                return right;
            }else{
                return mid;
            }
        }
        //arr[right]<=arr[left]
        else{
            if(arr[mid]<arr[right]){
                return right;
            }else if(arr[mid]>arr[left])
                return left;
            else{
                return mid;
            }
        }
    }
    //Hoare版快排
    private static int partition1(int[] arr,int start,int end){
        int i=start;
        int pivot=arr[start];
        while(start<end){
            while (start<end&&arr[end]>=pivot)
                end--;
            while(start<end&&arr[start]<=pivot)
                start++;
            swap(arr,start,end);
        }
        swap(arr,i,start);
        return start;
    }
    //挖坑法快排
    private static int partition2(int[] arr,int start,int end){
        int i=start;
        int temp=arr[start];
        while(start<end){
            while (start<end&&arr[end]>=temp)
                end--;
            arr[start]=arr[end];
            while(start<end&&arr[start]<=temp)
                start++;
            arr[end]=arr[start];
        }
        arr[start]=temp;
        return start;
    }
    public static  void mergeSort1(int[] arr){
        mergeSortFunc(arr,0,arr.length-1);
    }
    private static  void mergeSortFunc(int[] arr,int left,int right){
        if(left==right) return;
        int mid=(left+right)/2;
        //分解
        mergeSortFunc(arr,left,mid);
        mergeSortFunc(arr,mid+1,right);
        //归并
        merge(arr,left,mid,right);
    }
    private static void merge(int[] arr,int left,int mid,int right){
        int s1=left;
        int e1=mid;
        int s2=mid+1;
        int e2=right;
        int[] tempArr=new int[right-left+1];
        int k=0;
        while(s1<=e1&&s2<=e2){
            if(arr[s1]<=arr[s2]){
                tempArr[k++]=arr[s1++];
            }else{
                tempArr[k++]=arr[s2++];
            }
        }
        while (s1<=e1){
            tempArr[k++]=arr[s1++];
        }
        while (s2<=e2){
            tempArr[k++]=arr[s2++];
        }
        for (int i = 0; i <tempArr.length ; i++) {
            arr[i+left]=tempArr[i];
        }
    }
    public static void mergeSort3(int[] arr){
        int gap=1;
        while(gap<arr.length){
            for (int i = 0; i <arr.length ; i+=2*gap) {
                int left=i;
                int mid=left+gap-1;
                int right=mid+gap;
                if(mid>arr.length-1)
                    mid=arr.length-1;
                if(right>arr.length-1)
                    right=arr.length-1;
                merge(arr,left,mid,right);
            }
            gap*=2;
        }
    }
































}
